package demo1;

public class Partition {
    public static void main(String[] args) {
        ListNode l1 = new ListNode(12) ;
        ListNode l2 = new ListNode(11) ;
        ListNode l3 = new ListNode(10) ;
        ListNode l4 = new ListNode(15) ;
        ListNode l5 = new ListNode(9) ;
        l1.next = l2 ;
        l2.next = l3 ;
        l3.next = l4 ;
        l4.next = l5 ;
        ListNode h = partition(l1 , 11) ;
        dis(h);


    }

    public static ListNode partition(ListNode pHead, int x) {
        // write code here
        ListNode head  = null ;
          ListNode ret = pHead ;
          ListNode fast = ret.next ;
          while(fast != null){ 
            if(fast.val < x){
                if(head == null){
                    head = fast ;
                }
                ret.next = fast.next ;
                fast.next = ret ;
                ret = fast ;
                fast = fast.next.next ;
            }else{
                 fast = fast.next ;
            }

          }
          if(head == null){
            head = pHead ;
          }

          return  head ;

    }
    public static void dis(ListNode head){
        ListNode ret = head ;
        while(ret != null){
            System.out.print(ret.val + " ");
            ret = ret.next ;
        }
    }

}
